08. A*: Real-World Map
A*: Real-World Map
Now it’s time to apply the A* algorithm that you’ve coded earlier to a real-world map.
If you recall, this map is the one you generated with the occupancy grid mapping algorithm using both sonar and odometry data. Our aim is now to find the shortest path for the robot to cross from start o to goal * position.
Given
Map(
300x150
)
: The map data stored in the
map.txt
file in form of log odds values. As a reminder, here's how you should interpret these numbers:
- A cell is considered unknown if its log odds value is equal to 0 .
- A cell is considered as occupied if its log odds is larger than 0 .
- A cell is considered as free if its log odds value is less than 0 .
Grid(
300x150
)
: The log odds values converted to 0’s and 1’s where
0
represents the
free
space and
1
represents the
occupied
or
unknown
space.
Robot Start position:
230,145
Robot Goal Position:
60,50
Direction of Movement:
Up(
-1,0
) - left(
0,-1
) - down(
1,0
) - right(
0,1
)
Movement Arrows:
Up(
^
) - left(
<
) - down(
v
) - right(
>
)
Cost of Movement:
1
Heuristic Vector:
Manhattan
If you scroll down to the code, you will notice that I added three new functions to the Map class. I coded a
GetMap
function which reads the
map.txt
log odds values and assign them the
map
variable. You will code the
MapToGrid
function in order to convert the log odds values to 0’s and 1’s. These 0 and 1 values will be assigned to the
grid
variable. And finally, the
GeneratedHeuristic
function is another function that you have to code in order to generate a Manhattan-based heuristic vector by computing the Manhattan distance of each cell with respect to the goal position. As a reminder the Manhattan distance of each cell can be calculated as follow:
x_{d} = x_{goal} - x_{cellposition}
y_{d} = y_{goal} - y_{cellposition}
Manhattan \ distance \ d = \left | x_{d} \right | + \left | y_{d} \right |
A*: Real-World Map
Task Description:
Follow these instructions to generate the shortest path using the A* algorithm:
Task Feedback:
Great Job!
Start Quiz: